10067 - Playing with wheels/10067.3.cpp

   1 #include <iostream>
   2 #include <queue>
   3 #include <vector>
   4 #include <sstream>
   5
   6
   7 using namespace std;
   8
   9 int main(){
  10   int cases;
  11   cin >> cases;
  12   while (cases--){
  13     vector<bool> forbidden(10000, false);
  14     vector<bool> visited(10000, false);
  15
  16
  17     int start = 0;
  18     for (int i=0; i<4; ++i){
  19       int x; scanf("%d", &x);
  20       start = (start * 10) + x;
  21     }
  22
  23     int end = 0;
  24     for (int i=0; i<4; ++i){
  25       int x; scanf("%d", &x);
  26       end = (end * 10) + x;
  27     }
  28
  29     int n;
  30     cin >> n;
  31     while (n--){
  32       int f=0;
  33       for (int i=0; i<4; ++i){
  34         int x; scanf("%d", &x);
  35         f = (f * 10) + x;
  36       }
  37       forbidden[f] = true;
  38     }
  39
  40     queue<pair<int, int> > q;
  41     //El primer numero es el nodo que voy a visitar, el segundo es la minima distancia en que lo puedo visitar
  42     int answer = -1;
  43     q.push(make_pair(start, 0));
  44     while (!q.empty()){
  45       int node = q.front().first;
  46       int dist = q.front().second;
  47       q.pop();
  48
  49       if (node == end){
  50         answer = dist;
  51         break;
  52       }
  53
  54       if (!visited[node]){
  55         visited[node] = true;
  56         for (int i=1; i<=4; ++i){
  57           int pow10 = 1; for (int j=1; j<=i; ++j) pow10 *= 10;
  58           int digit = (node % pow10)* 10/pow10;
  59
  60           int v = node - digit * pow10/10;
  61
  62           int x = v + pow10/10 * ((digit+1)%10);
  63           int y = v + pow10/10 * ((digit+9)%10);
  64
  65           if (!forbidden[x] && !visited[x]){
  66             q.push(make_pair(x, dist + 1));
  67           }
  68           if (!forbidden[y] && !visited[y]){
  69             q.push(make_pair(y, dist + 1));
  70           }
  71
  72         }
  73       }
  74     }
  75     cout << answer << endl;
  76   }
  77   return 0;
  78 }